//      https://www.nowcoder.com/practice/4af96fa010c44638a7e112abf65f7237




class Solution
{
public:
    int LIS(vector<int>& a)
    {
        if (a.empty()) return 0;

        vector<int> dp;
        dp.push_back(a[0]);

        for (int i = 1; i < a.size(); ++i)
        {
            if (a[i] > dp.back())
            {
                dp.push_back(a[i]);
            }
            else
            {
                auto it = lower_bound(dp.begin(), dp.end(), a[i]);
                *it = a[i];
            }
        }

        return dp.size();
    }
};